1. Field of the Invention
The present invention relates to method and apparatus for detecting unreliable and/or compromised router/switches in a network by utilizing the redundancy of Link State routing protocols.
2. Related Art
Ad hoc wireless network systems, for example municipal or military radio communication systems (such as the Near Term Digital Radio proposed by the U.S. Army), typically route messages between mobile transceivers and routers. To efficiently manage message flow in the network, it is important for each router to have knowledge of the traffic in the network, and, in particular, the state of the links between the routers themselves, and between the routers and the mobile transceivers. The routers can then efficiently direct message flow to ensure overall system reliability and responsiveness. Thus, Link State routing information must be transmitted between the routers.
In existing wireless ad hoc networks, all of the nodes are equipped with wireless communication transceivers; some of the nodes are capable of network routing functions (“routers”), but others are merely sources or destinations for data traffic (“end points” such as radio transceivers). All nodes execute a set of algorithms and perform a set of networking protocols that enable each node to find the other nodes, to determine paths through the network for data traffic from source to destination, and to detect and repair ruptures in the network as the nodes move, fail, change battery-power, or communications path characteristics change over time (e.g. multipath distortions).
It is known to employ link state routing as a means of distributing routing information through the network to enhance traffic management. Link state routing is a well-known routing mechanism and will not be described in detail herein. See, for example, as described in technical articles including: “Packet Radio Routing,” by Gregory S. Lauer in Chapter 11 of “Routing in Communication Networks”, ed. Martha Steenstrup. Prentice-Hall 1995; “Packet Radio Network Routing Algorithms: A Survey,” by J. Hahn and D. Stolle, IEEE Communications Magazine, Vol. 22, No. 11, November 1984, pp. 41–47; “The Organization of Computer Resources into a Packet Radio Network,” by R. E. Kahn, IEEE Trans. On Communications, Vol. COM-25, No. 1, January 1977, pp. 169–178; “Analysis of Routing Strategies for Packet Radio Networks,” by J. Garcia-Luna-Aceves and N. Shacham, Proc. Of the IEEE INFOCOM '85, Washington, D.C., March 1985, 292–302; and “The DARPA Packet Radio Network Protocols,” by J. Jubin and J. Tornow, Proc. Of the IEEE, Vol. 75, No. 1, January 1987, pp. 21–32. See also U.S. Pat. Nos. 4,718,001; 5,243,592; 5,850,592; 5,881,246; and 5,913,921 for the general state of the art in wireless network message routing.
FIG. 1 shows a sample network topology. The circles (“nodes”) in this figure represent network routers. The lines (“links”) represent communications channels. Thus, Router A is directly connected to routers B, C, D, and E, and these are called A's “neighbors.” Again referring to FIG. 1, we see that Router B has neighbors A and C, that Router E has neighbors A and J, and so forth.
FIG. 2 displays a selected subset of the proper router status messages for the sample network topology. These router status messages, as illustrated, are a simplified form of the standard link-state routing updates that are commonly used in computer networking. (The simplifications are for expository clarity only; they do not affect the substance of this invention.)
We see that in link-state routing, each router is required to issue a router status message that (a) identifies the router that is reporting this information, and (b) lists all the neighbor routers for this report. Thus we have selected two status messages—one from router A and one from router B. As can be seen, each message identifies the reporting node and lists that node's neighbors.
These modern information networks can be attacked or degraded in a variety of ways including physically capturing a router and reconfiguring it to give out false router updates, or remotely penetrating the router and reconfiguring its router database with false information. Once the router is compromised, one method to disrupt the network involves creating false routing control traffic within the network so that user traffic is mis-routed or discarded. This type of attack can often be blocked or mitigated by physically securing access to the network routers and/or switches. However, in some open architecture networks, or in other situations in which routers/switches are in a semi-public place and cannot be effectively secured by purely physical means, additional techniques must be employed to help safeguard against such types of attacks. Even where the routers can be physically secure, the router may be attacked by remote insertion of false/corrupted data or viruses. In non-attack scenarios, certain routers/switches may degrade and become unreliable enough to introduce false routing information into the network. In these circumstances also, techniques must be found to identify the unreliable or compromised router and to isolate it and re-route network traffic.
Current Link State routing protocols include a redundancy feature in which each active router or switch (“node”) within a network is responsible for issuing reports (“routing updates”) on the current status of the communication links from that node to its neighboring nodes. The redundancy feature utilizes complementary reports between communicating links. Typically, each such report contains the information on the “simplex” link state, i.e., the state of the communication link from the reporting node to a neighbor node. However, each such report typically does not include information corresponding to the link from that neighbor back to the reporting node. This report contains routing update information including such fields as the reporting node's identifying number, its network address, identifiers for its communication links, the current state of the link (operational, in loopback, etc.), and one or more metrics for each link that indicate the suitability of that link for various types of message traffic. These reports are issued both periodically and on an event-driven basis, for example, when a link is first made operational, when it is removed from service, when it's metrics change, and so forth.
Although Link State routing protocols treat each communication link as a pair of independent simplex links, in reality the communications between the node and its neighbor are almost invariably bi-directional and act as a single, integrated link within the network architecture. In other words, in normal operation, router 10 reports that it has a functioning link to its neighbor router 12 “if and only if” router 12 correspondingly reports that it has a functioning link to router 10. This redundancy feature is exploited in the present invention. Note that the “if and only if” statement may be briefly false when the links change their state, since the two reporting routers are typically not synchronized and hence their updates will propagate through the entire network at slightly different times. After this short interval of dis-coordination, however, the statement will become true once again.
Thus, what is needed is a way to guard a network against an unreliable, degraded, or compromised router/switch, and preferably a way that utilizes the redundancy feature in Link State protocols.